package cn.LinkedList;


import java.util.Objects;

public class LinkedListDemo {

    public static void main(String[] args) {

        LinkList<String> list = new LinkList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");
        list.add("g");
        // list.add(0, "h");
        // list.add(7, "i");
        // list.add(3, "j");
        // list.clear();
        // System.out.println(list.indexOf("c"));
        // list.remove(6);
        System.out.println(list.subList(2, 6));
        System.out.println(list);
    }

}

// 模拟：LinkedList
class LinkList<E> {

    // 节点个数/元素个数
    private int size = 0;
    // 头节点
    private Node<E> first;
    // 尾节点
    private Node<E> last;

    // 添加元素
    public void add(E e) {
        // 创建节点来存储这个元素
        Node<E> node = new Node<>(null, e, null);
        // 判断是否是第一个元素
        if (size == 0) {
            this.first = this.last = node;
        } else {
            // 原来尾节点的下一个节点是新节点
            this.last.next = node;
            // 新节点的上一位是原来的为节点
            node.prev = this.last;
            // 新添的节点是尾节点
            this.last = node;
        }
        // 元素个数+1
        size++;
    }

    // 插入元素
    public void add(int index, E e) {
        // 判断下标越界
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        // 构建节点
        Node<E> n = new Node<>(null, e, null);
        if (index == size) { // 插入尾部
            add(e);
        } else if (index == 0) { // 插入头部
            // 新节点的下一位是原来的头节点
            n.next = this.first;
            // 原来的头节点的上一位是新节点
            this.first.prev = n;
            // 新节点是头节点
            this.first = n;
            size++;
        } else { // 中间插入
            // 获取指定下标上的节点
            Node<E> node = this.getNode(index);
            // 原节点上一位的下一个节点是现在的新节点
            node.prev.next = n;
            // 新节点的上一位是原节点的上一位
            n.prev = node.prev;
            // 新节点的下一位是原来的节点
            n.next = node;
            // 源节点的上一位是新节点
            node.prev = n;
            size++;
        }
    }

    // 获取指定下标对应的节点
    private Node<E> getNode(int index) {
        /*
        Node<E> n = this.first;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n;
         */
        int i;
        Node<E> n;
        if (index < size / 2) {
            // 下标
            i = 0;
            n = this.first;
            while (i < index) {
                n = n.next;
                i++;
            }
        } else {
            // 下标
            i = size - 1;
            n = this.last;
            while (i > index) {
                n = n.prev;
                i--;
            }
        }
        return n;
    }

    // 清空集合
    public void clear() {
        // 获取头节点
        this.first = this.last = null;
        size = 0;
    }

    // 获取指定元数第一次出现的下标
    public int indexOf(E e) {
        Node<E> n = this.first;
        for (int i = 0; i < size; i++) {
            if (Objects.equals(n.item, e)) return i;
            n = n.next;
        }
        return -1;
    }

    // 判断是否包含指定元素
    public boolean contains(E e) {
        return indexOf(e) != -1;
    }

    // 判断两个集合是否相等
    @Override
    public boolean equals(Object o) {
        // 判断地址是否一致
        if (this == o) return true;
        // 判断参数是否为空
        if (o == null) return false;
        // 判断类型是否一致
        if (this.getClass() != o.getClass()) return false;
        // 强转
        LinkList<E> list = (LinkList<E>) o;
        // 比较大小是否一致
        if (this.size != list.size) return false;
        // 比较元素是否一致
        Node<E> n1 = this.first;
        Node<E> n2 = list.first;
        for (int i = 0; i < size; i++) {
            if (!Objects.equals(n1.item, n2.item)) return false;
            n1 = n1.next;
            n2 = n2.next;
        }
        return true;
    }

    // 获取指定下标上的元素
    public E get(int index) {
        outOfBounds(index);
        return getNode(index).item;
    }

    // 判断越界
    private void outOfBounds(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    // 获取哈希码
    @Override
    public int hashCode() {
        int h = 0;
        Node<E> n = this.first;
        for (int i = 0; i < size; i++) {
            h = 31 * h + (n.item == null ? 0 : n.item.hashCode());
            n = n.next;
        }
        return h;
    }

    // 判断集合是否为空
    public boolean isEmpty() {
        return size <= 0;
    }

    // 获取元素最后一次出现的下标
    public int lastIndexOf(E e) {
        Node<E> n = this.last;
        for (int i = size - 1; i >= 0; i--) {
            if (Objects.equals(n.item, e)) return i;
            n = n.prev;
        }
        return -1;
    }

    // 移除指定下标位置上的元素
    public void remove(int index) {
        outOfBounds(index);
        if (size == 1) { // 只有一个节点
            this.first = this.last = null;
        } else if (index == 0) { // 头节点
            // 原来头节点的下一位是现在头节点
            this.first = this.first.next;
            // 头节点的上一位清空
            this.first.prev = null;
        } else if (index == size - 1) {
            // 原来尾节点的上一位是新的尾节点
            this.last = this.last.prev;
            // 尾节点的下一位清空
            this.last.next = null;
        } else {
            // 获取节点
            Node<E> n = this.getNode(index);
            // 原来节点的上一位的下一个节点指向原来的下一个节点
            n.prev.next = n.next;
            // 原来节点的下一位的上一个节点指向原来的上一个节点
            n.next.prev = n.prev;
            // 清空引用
            n.prev = null;
            n.next = null;
        }
        size--;
    }

    // 移除指定的元素(首次出现)
    public void remove(E e) {
        // 获取第一次出现的下标
        int index = indexOf(e);
        if (index != -1) remove(index);
    }

    // 替换指定下标位置上的元素
    public void set(int index, E e) {
        outOfBounds(index);
        // 获取这个下标对应的节点
        Node<E> n = this.getNode(index);
        n.item = e;
    }

    // 获取节点个数
//    public int size() {
//        return size;
//    }

    public int size(){
        return size;
    }

    // 截取子列表
    public LinkList<E> subList(int fromIndex, int toIndex) {
        // 判断下标是否合法
        if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
            throw new IllegalArgumentException();
        // 定义新的列表
        LinkList<E> list = new LinkList<>();
        // 获取起始下标对应的节点
        Node<E> n = this.getNode(fromIndex);
        for (int i = fromIndex; i < toIndex; i++) {
            list.add(n.item);
            n = n.next;
        }

        return list;
    }

    // 转化为数组
    public Object[] toArray() {
        // 定义数组
        Object[] os = new Object[size];
        // 遍历列表，向数组中添加元素
        Node<E> n = this.first;
        for (int i = 0; i < size; i++) {
            os[i] = n.item;
            n = n.next;
        }
        return os;
    }


    @Override
    public String toString() {
        // 判断是否是一个空集合
        if (size == 0) return "[]";
        // 拼接
        StringBuilder sb = new StringBuilder("[");
        Node<E> n = this.first;
        /*
        for (int i = 0; i < size; i++) {
            sb.append(n.item).append(", ");
            n = n.next;
        }
        */
        while (n != null) {
            sb.append(n.item).append(", ");
            n = n.next;
        }
        String s = sb.toString();
        // 截取
        s = s.substring(0, s.length() - 2);
        return s += "]";
    }

    // 定义内部类表示节点
    private static class Node<E> {
        Node<E> prev; // 上一个节点
        E item; // 元素
        Node<E> next; // 下一个节点

        public Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }

}

